(1) Field of the Invention
The present invention relates to a variable-length coding technique.
(2) Related Art
As digital still and video cameras have become widely used and communication technologies have advanced, image data compressing techniques are increasingly utilized. A representative example of such compressing techniques is the ISO-standardized Moving Picture Experts Group (MPEG) format.
The MPEG technique realizes image data compression in the following manner. A frame is divided into a plurality of blocks each consisting of a plurality of pixels, based on intraframe correlation. After this, the data in each block is subjected to a discrete cosine transform (DCT) operation, which is one of orthogonal transformations, quantized, and then variable-length coded.
The variable-length coding process is described in detail in the following. Based on the DCT coefficients obtained as a result of the DCT operation, a Level value, a Last value, and a Run value are generated. The Level value indicates a value of a nonzero DCT coefficient, the Last value indicates whether the nonzero DCT coefficient is the last in the block, and the Run value indicates the number of continuous zero DCT coefficients prior to the nonzero DCT coefficient. Then, a code is uniquely assigned to a combination of the generated Last value, Run value, and Level value. In the present specification, the combination of the Last value, Run value, and Level value is denoted as a combination (Last, Run, Level), and an absolute value of the Level value is referred to as a Level absolute value.
Here, the MPEG-4 format stipulates a variable-length code (VLC) table which defines a unique code for each combination (Last, Run, Level absolute value). In the following, each unique code defined on the VLC table is referred to as a VLC. A code to be assigned to a combination (Last, Run, Level) is generated by a VLC corresponding to a combination (Last, Run, Level absolute value) and a value indicating the sign of the Level value.
If there is no VLC corresponding to the combination (Last, Run, Level absolute value) on the VLC table, one of the following three escape modes is used to generate a code to be assigned to the combination (Last, Run, Level).
According to a first escape mode, an LMAX is retrieved from the VLC table, for the combination (Last, Run, Level absolute value). The LMAX is a maximum Level absolute value corresponding to the pair of the Last value and Run value. Subsequently, the retrieved LMAX is subtracted from the Level absolute value, so that New level (=the Level absolute value−the LMAX) is calculated. Following this, the VLC table is searched again for a VLC corresponding to a combination (Last, Run, New Level). If there is a corresponding VLC on the VLC table, based on the corresponding VLC, a code to be assigned to the combination (Last, Run, Level) is generated.
According to a second escape mode, an RMAX is retrieved for the combination (Last, Run, Level absolute value) from the VLC table. The RMAX is a maximum Run value corresponding to the pair of the Last value and Level absolute value. Subsequently, a value obtained by adding 1 to the retrieved RMAX is subtracted from the Run value, so that New Run (=the Run value−(the RMAX+1)) is calculated. Following this, the VLC table is searched to detect a VLC corresponding to a combination (Last, New Run, Level absolute value). If there is a corresponding VLC on the VLC table, a code is generated based on the corresponding VLC, and assigned to the combination (Last, Run, Level).
According to a third escape mode, a code having a fixed length is generated based on the combination (Last, Run, Level), and assigned to the combination (Last, Run, Level).
Conventionally, the VLC table is searched first for retrieving the VLC corresponding to the combination (Last, Run, Level absolute value). If detected, the retrieved VLC and the value indicating the sign of the Level value are used to generate a code assigned to the combination (Last, Run, Level).
If there is no VLC corresponding to the combination (Last, Run, Level absolute value) on the VLC table, a code generating operation is conducted according to the above-described first escape mode. If there is no VLC corresponding to the combination (Last, Run, New Level) on the VLC table, a code generating operation is conducted according to the second escape mode. If there is no VLC corresponding to the combination (Last, New Run, Level absolute value) on the VLC table, a code generating operation is conducted according to the third escape mode.
In the case of performing the variable-length coding process defined by MPEG-4 in this way, the VLC table needs to be searched many times until the fixed-length code is obtained as a last resort. This creates a problem of slow processing rate for data which requires the third escape mode frequently.
To solve this problem, a patent document 1 (Japanese patent application publication No. 2001-586928) discloses a variable-length coding method that uses three VLC tables for conducting the above-described four types of code generating operations, in parallel, based on a VLC corresponding to a combination (Last, Run, Level absolute value) and according to the first to third escape modes. As a result, four codes are generated. According to preset priorities among the generated four codes, an appropriate code is selected and output. By doing so, a time required for variable-length coding can be shortened.